1. Field of the Invention
This invention relates generally to computer systems and more particularly to a deadlock detection mechanism for detecting a situation where one or several processes are waiting for events which cannot happen.
2. Description of the Prior Art
Electronic computers have grown from first generation hardware characterized mainly by vacuum tubes, to second generation hardware characterized by transistors, to third generation hardware characterized, in the main, by integrated circuits. Along with these different generations of hardware there were different generations of software, wherein first generation software was characterized mainly by machine language, assemblers and subroutines, and second generation software was characterized by high-level languages, monitors and macro assemblers. Third generation software is characterized by operating systems, on-line real-time systems multiprogramming systems, and data management systems.
The first generation hardware in combination with first generation software, and also the second generation hardware in combination with second generation software were primarily oriented toward batch processing where jobs were executed primarily in serial fashion. Moreover, the third generation of hardware/software systems are also batch-process oriented; however because of the advent of multiprogramming, several jobs may be executed in parallel rather than serial, and permits the acceptance of input information for processing as it is generated.
The fourth generation system will typically be classified as a communication and control system capable of widely diversified processor applications, and will be stimulated primarily by transmitted data rather than by batch programs (i.e. system control will be established primarily by input rather than by operator action) wherein submission of information will generally be in real time.
Processing in first generation hardware/software computer systems was relatively straightforward where the job or program was considered the basic processing unit. For each user initiated job or transaction a program generally ran with little or no interruption until the job or transaction was completed. Many straightforward jobs such as the compilation and execution of a high level language program, such as FORTRAN, could and did run as a single process. More difficult jobs, however, would require multitask operations and they would create other processes as they ran. (Note that a process is a concept implying the carrying on of some activity and should not be confused with the concept of a program, which is a process or activity description and can be used by one or more processes. We can speak either of a process or a processor executing a program. See Glossary of Definitions).
The concept of a process as being the basic processing unit developed to fill a need for the multiprogramming/multiprocessing environment of third generation computers. In such an environment where many users are demanding service simultaneously, it is natural to conceive of multiple processes competing for resources within the computer system. Each process consists of a program (i.e. an ordered collection of instructions and other data associated with the instructions) which is executed by the computer processor and a process state vector which defines the current status of the process. The process operates on data to perform a user's job or some phase of that job. Where many such processes are demanding simultaneous attention from the system, the task of communicating with and between such processes and the task of controlling and allocating resources to such processes particularly in view of the requirements of fourth generation systems becomes extremely complex.
In a multiprogramming/multiprocessing environment, it is essential that cooperation between two or more processes be efficiently and expeditiously realized. While many solutions to this problem have been proposed in the past, the technique of interprocess communication and control needed for the fourth generation computers has not, until now, been fully realized. The germination of the concepts required for a fourth generation computer, however, have been partially developed by E. W. Dijkstra in a paper entitled "Cooperative Sequential Processes from Programming Languages", NATO Advanced Study Institute, edited by F. Genuys of Paris and published in Academic Press, 1968. In this paper, Dijkstra postulates a basic concept of a semaphore for use in process synchronization and "P" and "V" instructions operating upon the semaphore. Unfortunately, Dijkstra provides for interprocess communication and process synchronization solely by software usage thus not only slowing down the operating time of the system but also decreasing the efficiency and extending the overall overhead required for such a system. More importantly, Dijkstra does not provide the concepts required for any significant exploitation of a fourth generation computer since he formulates only a basic premise in process synchronization. For one example, the transmission of messages from one process to another is not anticipated nor explained in Dijkstra's paper.
The concepts of P and V instructions have also been previously expounded by Edsger W. Dijkstra in the previously cited article. However, these concepts are presented only in generalized terms and do not provide the system configuration needed in a fourth generation computer. Moreover, Dijkstra merely provides a software basis for interpreting and using P and V instructions. Thus the memory organization necessary for rapidly accessing processes in addition to providing a systematic reallocation of the data processor has not been contemplated. As a result, not only are many of the P and V instructions necessary for delivering or receiving data by the executing processes not shown by Dijkstra but also the hardware/firmware basis for enabling process transferral in response to all P and V instructions is not envisioned.
Moreover in a multiprocessing environment, interprocess communication and synchronization facilities are essential to achieve smooth cooperation between loosely connected processes. Primitive hardware mechanisms such as traps and interrupts were initially devised to fill basic system needs. More advanced facilities such as Dijkstra's semaphores described in Reference 1 infra were later introduced and have been widely applied in one form or another. Please refer to References 2-4 attached hereto as an appendix under the caption References. User-oriented software control structures such as event control blocks were also provided for user intertask communication in a multitasking environment.
While these facilities have proved useful in the resolution of many specific problems, they have failed to provide a broad and unified interprocess communication capability well suited to general system and user needs in asynchronous processing applications.
By asynchronous processing, we refer to the type of activity carried out by a sequential process (as defined in Reference 1) in response to signals that are generated independently and asynchronously from that process (by some other process or device). Examples of this type of processing include:
handling hardware-generated traps which signal the occurrence of exception conditions such as machine error, program error, overflow, etc.; PA1 handling hardware-generated interrupts which indicate the occurrence of significant external events including I/O transfer completion, I/O error detection, and timer run-out; PA1 processing software interrupts generated upon detection of unusual results within a procedure; or those triggered by calls to the system supervisor; PA1 processing activity performed by one software task in response to requests issued by some other task in a multitasking environment. PA1 the trend of computer architecture toward multiprocessor configurations for central as well as peripheral sub-systems. Typical of this trend is the use of multiple central processors, or separate front-end and network processors to enhance system performance and system availability; PA1 the trend toward distributed implementation of multiprogramming or time-sharing operation systems; PA1 the trend toward fast-response on-line application systems providing a broad variety of services to a community of simultaneous users.
Several trends are contributing to enhance the significance of asynchronous processing. Among these are:
What is required for the fourth generation computer is a system which automatically integrates process communication and process control so as to not only enhance the operating efficiency of the system but also to provide sufficient flexibility to deal with the innumerable situations arising in the transfer of information from one process to another and in the management of events and messages. The system is the subject of a U.S. patent application Ser. No. 462,551, disclosing an invention by the same inventors of the instant invention entitled "An Extended Semaphore Architecture" and filed on an even date with the instant application and assigned to the same assignee, and incorporated herein by reference.
In such a fourth generation architecture where each process is concerned with several event variables, the possibility of a deadlock situation is introduced, wherein two or more processes are permitted to wait for related events which cannot happen.